1. Technical Field
The invention relates to data communications networks. More particularly, the invention relates to an improved method and apparatus for managing the allocation of data capacity of a network composed of one or more physically shared network segments interconnected by packet routing devices. The invention manages the allocation of network capacity among devices attached to the various segments, where each shared network segment relies on collision avoidance and detection for managing on-demand network access within a baseband channel.
2. Description of the Prior Art
The seminal teaching for on-demand access to physically shared networks is described in R. Metcalfe, D. Boggs, C. Thacker, B. Lampson, Multipoint data communication system with collision detection, U.S. Pat. No. 4,063,220 (Dec. 13, 1977). The Metcalfe et al patent is presently referenced in 186 other patents. Examples of such networks are traditional Ethernet, IEEE Standard 802.3 for coaxial cable, and IEEE Standard 802.11 for local area wireless networking. Additionally, new technologies are being developed which provide Ethernet-like characteristics on other physical mediums, such as Category 1 or 2 unshielded twisted pairs or AC power lines.
A feature of most emerging shared-capacity technologies is that the achievable transmission rate between nodes on the network varies based on such factors as the node itself, topology of the network, and electrical noise. Such networking is often called rate-adaptive networking because each node adapts its basic transmission parameters to achieve the best rate to some other node. Unlike previous shared-capacity networks, it is not possible to describe the maximum bandwidth of the network, or to predict a priori the achievable data rate between any two nodes. This situation is becoming increasingly common with the interconnection of shared networks having different transmission speeds. For example, the family of IEEE 802 standard networks is designed for interconnection, yet the speed of each shared segment may range from a few magabits per second to gigabits per second.
As used herein, the generic term “ethernet” refers to any similar physically shared network segment. Fundamental characteristics of an ethernet are:                A number of nodes, each free to choose to transmit at any time;        An access-checking scheme, termed Carrier Sense Multiple Access (CSMA), in which a node checks if the shared network is in use before transmitting;        Collision Detection (CD), in which a node monitors the shared network as it is transmitting, to detect if another node began transmitting simultaneously, thus garbling the data; and        A random back-off algorithm which attempts to de-synchronize nodes which have sent colliding packets by having each node wait a (short) random amount of time before retrying the transmission.        
As used herein, the generic term “streaming media” refers to long-term, continues flows of digital information that must achieve a constant data rate measured over short periods. For example, consider a network device accepting network packets containing compressed audio data, and using that data to produce the corresponding audio signals that drive a speaker. The device has a packet buffer of some fixed size, and it is the responsibility of the sending device to insure that packets are delivered in a timely way such that the buffer never becomes empty, and that there is always room in the buffer for the next packet sent. This means that each packet in the stream must be sent at a constant interval, said interval being based on the transmission speed, buffer size, and rate at which the audio data are consumed. This interval may vary over short periods depending on the size of the receiving buffer. Larger buffers can smooth the effects of contention for the shared network as long as sufficient network bandwidth is available to sustain the long-term average delivery rate. For example, consider current streaming audio products that use the Internet for data transmission, such as Real Audio, or Windows Media Player. These work correctly as long as sufficient bandwidth and buffer capacity is available to hide any packet transmission delays in the network.
Large buffers are expensive in many ways, so it is desirable to use methods of transmitting streaming media that minimize the required receiving buffer size. For example, if the audio device described earlier is two-way, the use of large buffers results in a time-shift between the incoming and outgoing streams which is easily detectable and aurally annoying. The physical cost and implementation of large buffers can become significant for inexpensive devices, such as portable phones.
As used herein, the generic term “on-demand” refers to other digital information flows on the network. For example, data fetched by an Internet Web browser is usually formatted as packets of TCP data, but there is no time-sensitivity to how the packets actually flow through the network. Buffers for such traffic are assumed to be large and carefully managed in software. Ideally, it is desirable to mix streaming media and on-demand traffic arbitrarily on the network to achieve the most efficient use of the network bandwidth. However, the two types of traffic place conflicting requirements on the underlying network.
There have been many attempts in the past to design methods and apparatus to balance the requirements of these two types of traffic. The simplest of these networks is one in which the available network bandwidth is permanently divided between streaming media and on-demand traffic. Such networks are sometimes referred to as “isochronous” networks. A central bandwidth allocation manager schedules the bandwidth among competing devices. One flaw with such systems is that the bandwidth division is fixed, limiting both on-demand performance and the maximum streaming bandwidth that can be supported. The result is inefficient utilization of the network bandwidth and limited performance. Another limitation of such networks is that the failure of the bandwidth manager leads to failure of the entire network.
A great deal of work has gone into the creation of mixed-traffic management streams on token-ring networks. Much of this work has been codified by IEEE Standard 802.5. Physical or logical token-passing methods are used for managing access to the shared network. J. Bell, Method of Simultaneously Transmitting Isochronous and Nonisochronous Data On A Local Area Network, U.S. Pat. No. 4,587,650 (6 May 1986) discloses a general description of how this traffic management is handled on a token-ring network.
Token passing schemes have weaknesses that preclude their use in many environments. These include: a requirement that all nodes support the same bandwidth; that each node implement recovery schemes to reconstruct capacity allocations and prioritization if any node fails; and that each node provide automated network bypass in case it fails, increasing the cost of a node and lowering its reliability. Additionally, passing the tokens and data through intermediate, non-transmitting nodes adds latency and decreases capacity. Token-ring networks have fallen into technical disfavor versus ethernet networks in many applications for these reasons.
Another set of attempts to address these problems involve the use of slotted protocols, where the bandwidth of the shared media is explicitly subdivided into equal-length slots, creating a TDMA (Time-Domain Multiple Access) network. K. Crisler, M. Needham, Method for Multi-Purpose Utilization of Resource in a Communication System, U.S. Pat. No. 5,295,140 (15 Mar. 1994) and K. Sardana, Adaptive Hybrid Multiple Access Protocols, U.S. Pat. No. 5,012,469 (30 Apr. 1991) contain a good overview of these methods, which may be generally referred to as reservation protocols. In these methods, it is assumed that each node has sufficient capability to participate in a contention-based reservation protocol, resulting in long-term assignment of shared network capacity to particular nodes. A general feature of these methods is the complexity of the reservation protocol, which increases the cost to implement any given node and reduces the node's reliability. Additionally, these protocols require each node to advertise its desire for the resources of the network continuously to maintain the reservation. This is done to allow quick recovery from failed nodes, but it consumes additional network bandwidth that might be more gainfully used and increases node cost. Finally, the overall capacity of the network is lowered because it is not always possible to fill each fixed-size slot to capacity.
Other schemes have been proposed for managing bandwidth allocation which involve significant differences from the basic operation of an ethernet network. These schemes are not considered here because they involve proprietary techniques, specialized architectures, or hardware that is not commercially viable. A primary example are allocation techniques developed for Asynchronous Transfer Mode (ATM) networks, where each node has a dedicated path to a central controller.
It would be desirable to create a facility for managing any ethernet network to handle both streaming media and on-demand traffic, while achieving maximum possible efficiency and performance of the network. Many current efforts in this field center on extensions to the Internet Protocol (IP) to allow dynamic provisioning of bandwidth. These extensions, collectively named RSVP (Reservation Protocol), are designed to operate in a complex, heavily routed infrastructure where there is no a priori knowledge of the network configuration or available bandwidth, and where it is not possible to rely on a central controller. This leads to undesirable features in a simpler environment, such as a single shared network segment: large code size, slow setup and teardown of streams, and a requirement that every device support RSVP and all related protocols.
The chief flaw of RSVP in a single shared network environment is that it is a peer-to-peer protocol, and assumes intermediate routers are simply allocating and deallocating bandwidth within their backplane and at the network ports, such that notions of total available bandwidth and managed reservations are disallowed. In an environment where the devices share a physical network and the bandwidth between any two devices is arbitrary, the lack of such knowledge leads to conflicts between devices. This is a key issue, one as yet unresolved by any standard protocol specification.
It would be desirable to provide a method and apparatus that addresses the weaknesses of prior art in this field (as described above) within any interconnected set of ethernet networks where there is varying physical bandwidth between nodes on the network.